#include <stdio.h>
#include <stdlib.h>
typedef int ElemType; //定义元素类型为整型

typedef struct LNode{
    ElemType data; //数据域
    struct LNode *next; //指针域，指向下一个结点
}LNode, *LinkList;//LinkList为指向LNode的指针类型，即链表类型

// 创建链表（头插法）
void CreateList_L(LinkList *L, int n){
    *L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    if (*L == NULL){
        printf("Memory allocation failed\n" );
        return;
    }
    (*L)->next = NULL; //初始化头结点的指针域为空
    
    for (int i = 0; i < n; i++){
        LNode *p = (LNode *)malloc(sizeof(LNode)); //创建新结点
        if (p == NULL){
            printf("Memory allocation failed\n" );
            return;
        }
        scanf("%d", &p->data); //输入数据域
        p->next = (*L)->next; //将新结点插入到头结点之后
        (*L)->next = p; //更新头结点的指针域
    }
}

// 1. 插入节点 - 在指定位置插入
int InsertList_L(LinkList L, int pos, ElemType e){
    if (pos < 1) {
        printf("插入位置不合法！\n");
        return 0; // 插入失败
    }
    
    LNode *p = L; // p指向头结点
    int j = 0;
    
    // 寻找第pos-1个节点
    while (p != NULL && j < pos - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL) {
        printf("插入位置超出链表长度！\n");
        return 0; // 插入失败
    }
    
    // 创建新节点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {
        printf("内存分配失败！\n");
        return 0; // 插入失败
    }
    
    s->data = e; // 设置新节点的数据域
    s->next = p->next; // 新节点指向原第pos个节点
    p->next = s; // 第pos-1个节点指向新节点
    
    return 1; // 插入成功
}

// 2. 查找节点 - 按值查找
LNode* SearchList_L(LinkList L, ElemType e){
    LNode *p = L->next; // 从第一个数据节点开始
    
    while (p != NULL) {
        if (p->data == e) {
            return p; // 找到节点，返回指针
        }
        p = p->next;
    }
    
    return NULL; // 未找到，返回NULL
}

// 查找节点 - 按位置查找
LNode* GetElem_L(LinkList L, int pos){
    if (pos < 1) {
        return NULL; // 位置不合法
    }
    
    LNode *p = L; // p指向头结点
    int j = 0;
    
    // 寻找第pos个节点
    while (p != NULL && j < pos) {
        p = p->next;
        j++;
    }
    
    return p; // 返回找到的节点或NULL
}

// 3. 删除节点 - 按位置删除
int DeleteList_L(LinkList L, int pos){
    if (pos < 1) {
        printf("删除位置不合法！\n");
        return 0; // 删除失败
    }
    
    LNode *p = L; // p指向头结点
    int j = 0;
    
    // 寻找第pos-1个节点
    while (p != NULL && j < pos - 1) {
        p = p->next;
        j++;
    }
    
    if (p == NULL || p->next == NULL) {
        printf("删除位置超出链表长度！\n");
        return 0; // 删除失败
    }
    
    LNode *q = p->next; // q指向要删除的节点
    p->next = q->next; // 绕过要删除的节点
    free(q); // 释放内存
    
    return 1; // 删除成功
}

// 删除节点 - 按值删除
int DeleteByValue_L(LinkList L, ElemType e){
    LNode *p = L; // p指向头结点
    int found = 0;
    
    while (p->next != NULL) {
        if (p->next->data == e) {
            LNode *q = p->next; // q指向要删除的节点
            p->next = q->next; // 绕过要删除的节点
            free(q); // 释放内存
            found = 1;
            // 如果只需要删除第一个匹配的节点，可以break
            // break;
        } else {
            p = p->next;
        }
    }
    
    return found; // 返回是否找到并删除
}

// 显示链表函数
void DisplayList_L(LinkList L){
    LNode *p = L->next; //从第一个结点开始遍历
    if (p == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    printf("当前链表: ");
    while(p != NULL){
        printf("%d ", p->data); //输出结点数据
        p = p->next; //移动到下一个结点
    }
    printf("\n");
}

// 获取链表长度
int GetLength_L(LinkList L){
    int length = 0;
    LNode *p = L->next;
    
    while (p != NULL) {
        length++;
        p = p->next;
    }
    
    return length;
}

// 销毁链表
void DestroyList_L(LinkList L){
    LNode *p = L;
    
    while (p != NULL) {
        LNode *q = p->next;
        free(p);
        p = q;
    }
}

int main(){
    LinkList L;
    int n;
    
    printf("输入链表长度: ");
    scanf("%d", &n); //输入结点个数
    
    printf("输入%d个元素: ", n);
    CreateList_L(&L, n); //创建链表
    
    DisplayList_L(L); //显示初始链表
    printf("链表长度: %d\n", GetLength_L(L));
    
    // 演示插入操作
    int pos, value;
    printf("\n=== 插入操作演示 ===\n");
    printf("输入要插入的位置和值(位置 值): ");
    scanf("%d %d", &pos, &value);
    if (InsertList_L(L, pos, value)) {
        printf("插入成功！\n");
        DisplayList_L(L);
    }
    
    // 演示查找操作
    printf("\n=== 查找操作演示 ===\n");
    printf("输入要查找的值: ");
    scanf("%d", &value);
    LNode *found = SearchList_L(L, value);
    if (found != NULL) {
        printf("找到值为 %d 的节点！\n", value);
    } else {
        printf("未找到值为 %d 的节点！\n", value);
    }
    
    // 演示按位置查找
    printf("输入要查找的位置: ");
    scanf("%d", &pos);
    LNode *node = GetElem_L(L, pos);
    if (node != NULL) {
        printf("位置 %d 的节点值为: %d\n", pos, node->data);
    } else {
        printf("位置 %d 不存在！\n", pos);
    }
    
    // 演示删除操作 - 按位置删除
    printf("\n=== 删除操作演示 ===\n");
    printf("输入要删除的位置: ");
    scanf("%d", &pos);
    if (DeleteList_L(L, pos)) {
        printf("删除成功！\n");
        DisplayList_L(L);
    }
    
    // 演示删除操作 - 按值删除
    printf("输入要删除的值: ");
    scanf("%d", &value);
    if (DeleteByValue_L(L, value)) {
        printf("删除成功！\n");
        DisplayList_L(L);
    } else {
        printf("未找到值为 %d 的节点！\n", value);
    }
    
    // 销毁链表
    DestroyList_L(L);
    
    return 0;
}